1. Field of the Invention
The present invention relates generally to an improved data processing system and in particular to a method and system for processing data. Still more particularly, the present invention is directed to a computer implemented method, system, and computer usable program code for managing data in a cache.
2. Description of the Related Art
A cache is a section of memory that stores frequently used data by a processor. Typically, the processor uses the cache to reduce time required to access data from main memory. In other words, the cache is a memory bank that bridges main memory and the processor. The cache is faster, or has a reduced latency, than main memory and allows the processor to execute instructions and read and write data at higher speeds. However, the cache is small compared to the main memory, so space is at a premium. Instructions and data are transferred from main memory to the cache in lines or blocks, possibly using some kind of look-ahead algorithm.
A level 1 (L1) cache is a memory bank, such as processor registers, built into the processor chip. The L1, or primary cache, is the memory closest to the processor, itself. A level 2 (L2) cache is a secondary staging area that feeds the L1 cache. The L2 cache may also be built into the processor chip or may reside on a separate chip on the motherboard. If the L2 cache is built into the processor chip, then a cache on the motherboard may be a Level 3 (L3) cache. The L3 cache feeds the L2 cache, which feeds the L1 cache, which feeds the processor. In addition, the L1 cache is faster than the L2 cache, which is faster than the L3 cache, which is faster than main memory. In other words, the latency increases as the memory hierarchy moves away from the processor. So, keeping “hot” data close to the processor is a desirable condition.
When a processor needs data from main memory, the needed data is brought into the L2 cache. If the processor does not reference that data for a certain amount of time, a cache replacement mechanism moves that data out of the L2 cache into the L3 cache. If the processor again needs that data, then that data is moved back into the L2 cache from the L3 cache. On the other hand, if that data is not referenced in the L3 cache for a certain amount of time, then that data is moved out of the L3 cache back into main memory.
The Least Recently Used (LRU) algorithm is widely employed for data management in a cache. The LRU algorithm replaces a cache line in the cache that the processor has not referenced or accessed for the longest period of time. The LRU algorithm is based on an observation that cache lines, which the processor referenced in the recent past, will most likely be referenced again in the near future.
Currently, when a cache line is removed from the L2 cache, the cache line is moved to the L3 cache and is given the highest ranking in the L3 cache by the LRU algorithm because the cache line is the newest referenced entry in the L3 cache. However, a drawback with this current cache line ranking method is that it only takes into account that the removed cache line is the least recently used among the set of cache lines presently in the L2 cache. This current cache line ranking method does not take into account that during the time the removed cache line was resident in the L2 cache, the processor may have accessed that cache line more frequently than many of the other L2 cache lines. In other words, in terms of performance that cache line was “hot,” but because the processor did not recently access that cache line in the L2 cache, that cache line is moved out to the L3 cache.
Removal of this once hot cache line from the L2 cache, and possibly from the L3 cache as well, may be due to the fact that many new memory references pushed that cache line out of the limited cache space. When the processor makes many new memory references, this once hot cache line falls victim to the LRU algorithm. The LRU algorithm pushes the once hot cache line out of the L2 and L3 caches to make room for these new entries. However, the processor may reference these new entries only once and then may again need to access the once hot cache line.
Therefore, it would be beneficial to have a computer implemented method, system, and computer usable program code for preserving a hot cache line in a lower level cache using an improved ranking mechanism to efficiently make use of premium cache space, while reducing latency.